package com.leetcode.offer;

/**
 * @author zfl
 * @Classname MissingNumber
 * @Description 0 ~ n-1 中缺失的数字
 * @Date 2020/11/27 16:22
 */
public class MissingNumber {

    /**
     * @param nums
     * @return
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.9 MB, 在所有 Java 提交中击败了81.57%的用户
     */
    public static int missingNumber(int[] nums) {
        int left = 0, right = nums.length - 1, mid = 0;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if(nums[mid] == mid) {
                left = mid + 1;
            }else if(nums[mid] > mid) {
                right = mid - 1;
            }
        }
        return left;
    }
}
